<?PHP

// I is the infinite distance.
include "config.php";
$querysi = "truncate table cetak";
$addsi = mysql_query($querysi);
define('I',10000000000000000000000000000000);
$query = "update jalur set cek = 0 where cek != 0";
$add = mysql_query($query);
$queryis = "update jalur set jalur = 0 where jalur != 0";
$addis = mysql_query($queryis);
$from = $_GET['a'] *1;
$to = $_GET ['b'] *1;
// Size of the matrix
$matrixWidth = 20;
$result = mysql_query("SELECT count(*) FROM `simpul`");
$row = mysql_fetch_row($result);
$no = $row[0];
$points = array();
for($i = 1; $i <= 1000; $i++) {
	$result1 = mysql_query("SELECT id1,id2,jarak FROM `simpul` where id =$i");
	$row1 = mysql_fetch_row($result1);
	for ($j = 0; $j < 3; $j++) {
		$points[$i][$j] = $row1[$j];
		//echo $row1[$j]."<br>";;
	}
}




$ourMap = array();
 
 
// Read in the points and push them into the map
 
for ($i=0,$m=count($points); $i<$m; $i++) {

	$x = $points[$i][0];
	$y = $points[$i][1];
	$c = $points[$i][2];
	$ourMap[$x][$y] = $c;
	$ourMap[$y][$x] = $c;
}
 
// ensure that the distance from a node to itself is always zero
// Purists may want to edit this bit out.
 
for ($i=0; $i < $matrixWidth; $i++) {
    for ($k=0; $k < $matrixWidth; $k++) {
        if ($i == $k) $ourMap[$i][$k] = 0;
    }
}
 
 
// initialize the algorithm class
$dijkstra = new Dijkstra($ourMap, I,$matrixWidth);
 
// $dijkstra->findShortestPath(0,13); to find only path from field 0 to field 13...
$dijkstra->findShortestPath($from); 
 
// Display the results
 
echo '<pre>';
//echo "the map looks like:\n\n";
//echo $dijkstra -> printMap($ourMap);
//echo "\n\nthe shortest paths from point:\n";
$coba = $dijkstra -> getResults($to);
echo '</pre>';





class Dijkstra {
 
	var $visited = array();
	var $distance = array();
	var $previousNode = array();
	var $startnode =null;
	var $map = array();
	var $infiniteDistance = 0;
	var $bestPath = 0;
	var $matrixWidth = 0;
 
	function Dijkstra(&$ourMap, $infiniteDistance) {
		$this -> infiniteDistance = $infiniteDistance;
		$this -> map = &$ourMap;
		$this -> bestPath = 0;
	}
 
	function findShortestPath($start,$to = null) {
		$this -> startnode = $start;
		foreach (array_keys($this->map) as $i) {
			if ($i == $this -> startnode) {
				$this -> visited[$i] = true;
				$this -> distance[$i] = 0;
			} else {
				$this -> visited[$i] = false;
				$this -> distance[$i] = isset($this -> map[$this -> startnode][$i]) 
					? $this -> map[$this -> startnode][$i] 
					: $this -> infiniteDistance;
			}
			$this -> previousNode[$i] = $this -> startnode;
		}
 
		$maxTries = count($this->map);
		$tries = 0;
		while (in_array(false,$this -> visited,true) && $tries <= $maxTries) {			
			$this -> bestPath = $this->findBestPath($this->distance,array_keys($this -> visited,false,true));
			if($to !== null && $this -> bestPath === $to) {
				break;
			}
			$this -> updateDistanceAndPrevious($this -> bestPath);			
			$this -> visited[$this -> bestPath] = true;
			$tries++;
		}
	}
 
	function findBestPath($ourDistance, $ourNodesLeft) {
		$bestPath = $this -> infiniteDistance;
		$bestNode = 0;
		for ($i = 0,$m=count($ourNodesLeft); $i < $m; $i++) {
			if($ourDistance[$ourNodesLeft[$i]] < $bestPath) {
				$bestPath = $ourDistance[$ourNodesLeft[$i]];
				$bestNode = $ourNodesLeft[$i];
			}
		}
		return $bestNode;
	}
 
	function updateDistanceAndPrevious($obp) {		
		foreach (array_keys($this->map) as $i) {
			if( 	(isset($this->map[$obp][$i])) 
			    &&	(!($this->map[$obp][$i] == $this->infiniteDistance) || ($this->map[$obp][$i] == 0 ))	
				&&	(($this->distance[$obp] + $this->map[$obp][$i]) < $this -> distance[$i])
			) 	
			{
					$this -> distance[$i] = $this -> distance[$obp] + $this -> map[$obp][$i];
					$this -> previousNode[$i] = $obp;
			}
		}
	}
 
	function printMap(&$map) {
		$placeholder = ' %' . strlen($this -> infiniteDistance) .'d';
		$foo = '';
		for($i=0,$im=count($map);$i<$im;$i++) {
			for ($k=0,$m=$im;$k<$m;$k++) {
				$foo.= sprintf($placeholder, isset($map[$i][$k]) ? $map[$i][$k] : $this -> infiniteDistance);
			}
			$foo.= "\n";
		}
		return $foo;
	}
 
	function getResults($batas) {
		$ourShortestPath = array();
		$foo = '';
		foreach (array_keys($this->map) as $i) {
			if($to !== null && $to !== $i) {
				continue;
			}
			$ourShortestPath[$i] = array();
			$endNode = null;
			$currNode = $i;
			$ourShortestPath[$i][] = $i;
			
			while ($endNode == null || $endNode != $this -> startnode) {
				$ourShortestPath[$i][] = $this -> previousNode[$currNode];
				$endNode = $this -> previousNode[$currNode];
				$currNode = $this -> previousNode[$currNode];
				
			
			}
			$ourShortestPath[$i] = array_reverse($ourShortestPath[$i]);
			
			if ($i === $batas) {
			if($this -> distance[$i] >= $this -> infiniteDistance) {
				$foo .= sprintf("no route from %d to %d. \n",$this -> startnode,$i);

			} else {
				
				$foo .= sprintf('%d => %d = %d [%d]: (%s).'."\n" ,
						$this -> startnode,$i,$this -> distance[$i],
						count($ourShortestPath[$i]),
						implode('-',$ourShortestPath[$i]));
				$aku = implode('-',$ourShortestPath[$i]);
				$akus = explode ('-',$aku);
				$a = 0;
				$j = 0;
				while ($a <= count($ourShortestPath[$i])){
				$a++;
				//$akus[$a]."<br>";
				$query = "update jalur set cek = $a where id = $akus[$a]";
				$add = mysql_query($query);
				
				$q = $akus[$a] * 1;
				
				$result1 = mysql_query("SELECT idt FROM `jalur` where id = $q"); 
				$row1 = mysql_fetch_row($result1);
				$id1 = $row1[0]*1;
				
				//$queryi = "update jalur set jalur = $a where idt = $id1";
				//$addi = mysql_query($queryi);
				
				//------
				
				

				
		
				$result3 = mysql_query("SELECT max(jalur)FROM `jalur` where jalur != 0"); 
				$row3 = mysql_fetch_row($result3);
				$max = $row3[0]+1;
				
				
				$result2 = mysql_query("SELECT min(id), count(id) FROM `jalur` where idt = $id1"); 
				$row2 = mysql_fetch_row($result2);
				$min = $row2[0];
				$hitung = $row2[1];
				
				$cek = mysql_query("SELECT id from jalur where idt = $id1 && cek != 0");
				$cek = mysql_fetch_row($cek);
				
				if ($min == $cek [0]){
				$aku = 1;
				} else {
				$aku = -1;
				}

				
				
				for ($x = 0; $x < $hitung; $x++) { 
				$j++;
				$titik = $min + ($aku*$x);
				$queryi = "update jalur set jalur = $j where id = $titik";
				$addi = mysql_query($queryi);
				
				$ceki = mysql_query("SELECT lat, lng from jalur where id = $titik");
				$ceki = mysql_fetch_row($ceki);
				$lati = $ceki[0];
				$lngi = $ceki[1];
				
				$qu = "INSERT INTO cetak (lat, lng) VALUES ($lati, $lngi)";
				$adde = mysql_query($qu);


					}
				
				
				//-----
				}
				$coba = $this -> distance[$i];
				//echo $coba."<br>";
			
			}
			$foo .= str_repeat('-',20) . "\n";
				if ($to === $i) {
					break;
				}
				
			}
		}
		return $coba;
	}
} // end class 

echo "<meta http-equiv='refresh' content='0;url=http://nusantaraview.web.id/PETA/index.php?a=$coba'>";
?>